package easyLeetcode;

import java.util.HashMap;
import java.util.Stack;

/*
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
* */
public class Leetcode_5 {
    public static void main(String[] args) {
        System.out.println(isValid("{()}"));
        System.out.println(isValid("[()}"));
        System.out.println(isValid("({)}"));
    }

    public static boolean isValid(String s) {
        //创建栈
        Stack<Character> stack = new Stack<>();

        // 创建一个哈希表，用于快速查找每个右括号对应的左括号
        HashMap<Character, Character> map = new HashMap<>();
        map.put('}', '{');
        map.put(')', '(');
        map.put(']', '[');

        for (char c : s.toCharArray()) {

            //如果是右括号
            if (map.containsKey(c)) {
                //条件1：栈顶为空:说明右括号是第一个元素，无法匹配
                //条件2：栈顶元素与value不匹配：括号错乱 例如 :([)]
                if (stack.isEmpty() || stack.pop() != map.get(c)) {
                    return false;
                }
            } else {  //左括号进栈
                stack.push(c);
            }
        }

        return stack.isEmpty();
    }
}
